// https://www.lintcode.com/problem/jump-game-ii/

public class Solution {
    /**
     * @param A: A list of integers
     * @return: An integer
     */
    public int jump(int[] A) {
        // write your code here
        /*
        这题比想象的要难，Google之后才找到一个纯线性的解法。先想明白下面2点：
        1. 从0出发，只需要1步就能覆盖A[1]到A[A[0]]，不可能更少。
        2. 那么1 <= i <= A[0]能到达的最远点i + A[i]的步数不可能多于2步。
        */
        if (A.length >= 2) {
            int ret = 1;
            int i = 1;
            int curr = A[0]; // 当前步数覆盖的最远距离
            int next = A[0]; // 当前步数内下一步能到的最远距离
            while (i <= Math.min(A.length, curr)) {
                next = Math.max(next, A[i] + i);
                if (i == (A.length - 1)) {
                    return ret;
                }
                if (i == curr) { // 到curr后面的点必须加一步
                    curr = next;
                    ++ret;
                }
                ++i;
            }
        }
        return 0;
    }
}